package com.leetcodehot.problems;

import java.util.Arrays;

public class problems377 {
    private int[] nums;
    private int[] memo;

    public int combinationSum4(int[] nums, int target) {
        this.nums = nums;
        this.memo = new int[target + 1];
        Arrays.fill(memo, -1); // -1 表示没有计算过
        return dfs(target);
    }

    private int dfs(int target) {
        if (target == 0) {
            return 1;
        }
        if (target < 0) {
            return 0;
        }
        if (memo[target] != -1) {
            return memo[target];
        }

        int res = 0;
        for (int x : nums) {
            res += dfs(target - x);
        }
        return memo[target] = res;
    }
}
